package com.kavinz.algo.list;

import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

/**
 * <Cracking the coding interview> #2.1 -- deleteDuplicates() <Cracking the
 * coding interview> #2.2 -- findNthToLast(int n)
 * 
 * @author Kevin Zhao
 * 
 */
public class SingleLinkedList<E> implements List<E> {
	// head of all the nodes in the list
	SingleNode firstNode;
	// the last node in the list
	SingleNode lastNode;

	// size of the list
	int size = 0;

	/**
	 * Every item inserted into SingleLinkedList will be stored into
	 * SingleNode.item which will have a link to the following one;
	 * 
	 * @author Kevin Zhao
	 */
	class SingleNode {
		E item;
		SingleNode next;

		public SingleNode(E item, SingleNode next) {
			this.item = item;
			this.next = next;
		}

		@Override
		public int hashCode() {
			return item.hashCode();
		}

		@Override
		public boolean equals(Object obj) {
			if (!(obj instanceof SingleLinkedList.SingleNode))
				return false;

			SingleNode another = ((SingleNode) obj);
			if (this.item == another.item || this.item.equals(another.item))
				return true;
			else
				return false;
		}

	}

	/**
	 * Exercise:<Cracking the coding interview> #2.1 (without a buffer) remove
	 * any duplication among all the nodes of the list. Note:Duplication is
	 * definded as two SingleNodes are equall
	 */
	public void deleteDuplicates() {
		SingleNode currentNode = firstNode;
		// currentNode pointer iteration
		while (currentNode != null) {
			SingleNode preRunningNode = currentNode;
			SingleNode runningNode = currentNode.next;
			// 1.1 runningNode pointer iteration
			while (runningNode != null) {
				// 1.1.1 find duplication
				if (runningNode.equals(currentNode)) {
					// 1.1.2 remove runningNode
					preRunningNode.next = runningNode.next;
					size--;

					if (runningNode == lastNode)
						lastNode = preRunningNode;
				}
				// 1.1.3 update
				preRunningNode = runningNode;
				runningNode = runningNode.next;
			}
			// 1.2 Increment
			currentNode = currentNode.next;
		}
	}

	/**
	 * Exercise:<Cracking the coding interview> #2.2 Implement an algorithm to
	 * find the nth to last element of a singly linked list
	 */
	public E findNthToLast(int n) {
		// check if the index is valid
		if (!isPositionIndex(n))
			throw new IndexOutOfBoundsException("index out of bounds");

		int index = this.size - n - 1;
		SingleNode node = firstNode;
		for (int i = 0; i < index; i++) {
			node = node.next;
		}
		return node.item;
	}

	/**
	 * Exercise:<Cracking the coding interview> #2.3 Implement an algorithm to
	 * delete a node in the middle of a single linked list, given only access to
	 * that node EXAMPLE Input: the node ‘c’ from the linked list a->b->c->d->e
	 * Result: nothing is returned, but the new linked list looks like
	 * a->b->d->e
	 * 
	 * Note:this solution will malfunction when the given n is the last node in
	 * the list
	 */
	public boolean deleteNode(SingleNode n) {
		if (n == null || n.next == null) {
			return false; // Failure
		}
		SingleNode next = n.next;
		n.item = next.item;
		n.next = next.next;
		return true;
	}

	public int size() {
		return this.size;
	}

	public boolean isEmpty() {
		return this.size == 0;
	}

	public boolean contains(Object o) {
		// TODO Auto-generated method stub
		return false;
	}

	public Iterator<E> iterator() {
		// TODO Auto-generated method stub
		return null;
	}

	public Object[] toArray() {
		// TODO Auto-generated method stub
		return null;
	}

	public <T> T[] toArray(T[] a) {
		// TODO Auto-generated method stub
		return null;
	}

	/**
	 * insert the given item at the tail of the list
	 */
	public boolean add(E value) {
		// construct a new node
		SingleNode newNode = new SingleNode(value, null);
		// if the list is empty
		if (this.size == 0) {
			this.firstNode = newNode;
			this.lastNode = newNode;
			size++;
			return true;
		}
		// if the list is non-empty
		else {
			// append the newNode to the tail of the list
			lastNode.next = newNode;
			this.lastNode = newNode;
			size++;
			return true;
		}
	}

	/**
	 * go through the list starting from the firstNode and find the node at the
	 * specified index <br>
	 * Time Complexity:
	 * 
	 * @param index
	 * @return
	 */
	private SingleNode traverse(int index) {
		SingleNode node = firstNode;
		for (int i = 0; i < index; i++) {
			node = node.next;
		}
		return node;
	}

	/**
	 * insert the element at the specified index of the list
	 */
	public void add(int index, E element) {
		// check if the index is valid
		if (!isPositionIndex(index))
			throw new IndexOutOfBoundsException("index out of bounds");
		if (index == size) {
			add(element);
			return;
		}
		// find neighboring nodes
		SingleNode precedingNode = traverse(index - 1);
		SingleNode followingNode = precedingNode.next;
		// insertion
		SingleNode newNode = new SingleNode(element, null);
		if (precedingNode == firstNode) {
			newNode.next = firstNode;
			firstNode = newNode;
		} else {
			precedingNode.next = newNode;
			newNode.next = followingNode;
		}
		size++;
	}

	public boolean remove(Object o) {
		// TODO Auto-generated method stub
		return false;
	}

	public boolean containsAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}

	public boolean addAll(Collection<? extends E> c) {
		// TODO Auto-generated method stub
		return false;
	}

	public boolean addAll(int index, Collection<? extends E> c) {
		// TODO Auto-generated method stub
		return false;
	}

	public boolean removeAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}

	public boolean retainAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}

	public void clear() {
		// TODO Auto-generated method stub

	}

	public E get(int index) {
		SingleNode node = traverse(index);
		return node == null ? null : node.item;
	}

	public E set(int index, E element) {
		// TODO Auto-generated method stub
		return null;
	}

	/**
	 * Tells if the argument is the index of a valid position for an iterator or
	 * an add operation.
	 */
	private boolean isPositionIndex(int index) {
		return index >= 0 && index <= size;
	}

	/**
	 * Tells if the argument is the index of an existing element.
	 */
	private boolean isElementIndex(int index) {
		return index >= 0 && index < size;
	}

	public E remove(int index) {
		// check if the index is valid
		if (!isElementIndex(index))
			throw new IndexOutOfBoundsException("index out of bounds");
		// deletion
		if (index == 0) {
			if (firstNode == null)
				return null;
			E item = firstNode.item;
			firstNode = firstNode.next;
			size--;
			return item;
		} else {
			// find neighboring nodes
			SingleNode precedingNode = traverse(index - 1);
			SingleNode followingNode = precedingNode.next;
			precedingNode.next = followingNode.next;
			size--;
			return followingNode.item;
		}
	}

	public int indexOf(Object o) {
		// TODO Auto-generated method stub
		return 0;
	}

	public int lastIndexOf(Object o) {
		// TODO Auto-generated method stub
		return 0;
	}

	public ListIterator<E> listIterator() {
		// TODO Auto-generated method stub
		return null;
	}

	public ListIterator<E> listIterator(int index) {
		// TODO Auto-generated method stub
		return null;
	}

	public List<E> subList(int fromIndex, int toIndex) {
		// TODO Auto-generated method stub
		return null;
	}

	public static void main(String[] args) {
		SingleLinkedList<String> list = new SingleLinkedList<String>();

		list.add("abcd");
		list.add("bbdd");
		list.add(2, "ccde");
		list.add(0, "ffas");
		list.add("zzz");
		list.add("zzz");

		/** Test for remove() *******/
		// list.remove(0);

		// list.deleteDuplicates();
		/** Test for findNthToLast() *******/
		// System.out.println(list.findNthToLast(6).toString());

		/** Test for sum() *******/
		SingleLinkedList a = new SingleLinkedList();
		SingleLinkedList b = new SingleLinkedList();
		a.add(3);
		a.add(1);
		a.add(5);
		b.add(5);
		b.add(9);
		b.add(2);

		SingleLinkedList result = list.sum(a, b);
		for (int i = 0; i < result.size; i++) {
			System.out.println(result.get(i).toString());
		}

		/** Test for other *******/
		// for (int i = 0; i < list.size; i++) {
		// System.out.println(list.get(i).toString());
		// }
	}

	/**
	 * Exercise:<Cracking the coding interview> #2.4 You have two numbers
	 * represented by a linked list, where each node contains a sin- gle digit
	 * The digits are stored in reverse order, such that the 1’s digit is at the
	 * head of the list Write a function that adds the two numbers and returns
	 * the sum as a linked list EXAMPLE Input: (3 ->1 -> 5) + (5 -> 9 -> 2)
	 * Output: 8 -> 0 -> 8
	 * 
	 * @param a
	 * @param b
	 * @return
	 */
	public SingleLinkedList sum(SingleLinkedList a, SingleLinkedList b) {
		SingleLinkedList result = new SingleLinkedList();

		SingleLinkedList host = null;
		SingleLinkedList guest = null;
		if (a.size > b.size) {
			host = a;
			guest = b;
		} else {
			host = b;
			guest = a;
		}

		for (int i = 0; i < host.size; i++) {
			Integer dataA = Integer.parseInt(host.get(i).toString());
			Integer dataB = Integer.parseInt(guest.get(i).toString());

			Integer sum = dataA
					+ dataB
					+ Integer.parseInt(result.get(i) == null ? "0" : result
							.get(i).toString());

			String sumString = String.valueOf(sum);
			if (sum >= 10) {
				result.add(i, sumString.charAt(1));
				result.add(i + 1, sumString.charAt(0));
			} else {
				result.add(i, sumString);
			}
		}

		result.remove(result.size - 1);
		return result;
	}


}
